
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define		SIZE	50

int del_substr(char *str, char const *substr);
int kmp_search(char const *str, int slen, char const *substr, 
				int plen, int const *nextval, int pos);
void get_nextval(char const *substr, int plen, int *nextval);


int 
main()
{
	char str[SIZE], substr[SIZE];

	printf("Input source chars and sub chars:\n");
	scanf("%s", substr);
	
	int plen = strlen(substr);

	int *nextval = (int *)malloc(plen * sizeof(int));

	get_nextval(substr, plen, nextval);
	free(nextval);
	nextval = NULL;

	return 0;
	}

void test()
{
	char str[SIZE], substr[SIZE];

	printf("Input source chars and sub chars:\n");
	scanf("%s%s", str, substr);

	del_substr(str, substr);

	printf("After delete the source chars is :%s\n", str);
//	return 0;
}

int 
del_substr(char *str, char const *substr)
{
	assert(str != NULL && substr != NULL);

	int slen, plen;

	slen = strlen(str);
	plen = strlen(substr);

	int *nextval = (int *)malloc(plen * sizeof(int));

	get_nextval(substr, plen, nextval);

	int flag = kmp_search(str, slen, substr, plen, nextval, 0);

	if (flag != -1) {
		int 	i = flag;
		int 	j = i + plen;

		while(str[j] != '\0') {
			str[i++] = str[j++];
		}
		str[i] = '\0';
	}
	free(nextval);
	nextval = NULL;
	return 0;
}


// 采用kmp算法实现查找；

int 
kmp_search(char const *str, int slen, char const *substr, int plen, int const *nextval, int pos)
{
	int 	i = pos;
	int 	j = 0;

	while (i < slen && j < plen) {
		if (j == -1 || str[i] == substr[j]) {
			i++;
			j++;
		} else {
			j = nextval[j];
		}
	}

	if (j >= plen)
		return i - plen;
	else 
		return -1;

}


void 
get_nextval(char const *substr, int plen, int *nextval)
{
	int 	i = 0;

	nextval[i] = -1;

	int 	j = -1;

	while (i < plen -1) {
		if (j == -1 || substr[i] == substr[j]) {
			i++;
			j++;

			if (substr[i] != substr[j])
				nextval[i] = j;
			else 
				nextval[i] = nextval[j];
		} else {
			j = nextval[j];
		}
	}

	for (i = 0; i < plen; i++) {
		printf("%d  ", nextval[i]);
	}
	printf("\n");
}
